package interview.tree;

import algorithm.model.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 非递归，二叉树中序遍历
 * 使用栈,因为递归其实也是入栈和出栈
 * Created by yzy on 2021-03-10 19:23
 */
public class MidTraversal {

    public static void main(String[] args) {
        TreeNode root = TreeNode.getTreeNode(new Integer[]{1,2,3,4,5,6,7});
        System.out.println(midTraversal(root));
    }

    public static List<Integer> midTraversal(TreeNode root){
        List<Integer> valList = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.empty()){
            TreeNode node = stack.pop();
            valList.add(node.val);
            if(node.right != null) stack.push(node.right);
            if(node.left != null) stack.push(node.left);
        }
        return valList;
    }

}
